package com.gwcloud.leetcode.offers;

/** 
* @ClassName   : Leetcode0470 
* @author      : ganwei 
* @date        : 2020年6月6日 
* @Description : TODO 
*/
public class Leetcode0470 {
	int result = Integer.MIN_VALUE;
	/**
	 * -解题思路，回溯
	 */
    public int maxValue(int[][] grid) {
    	if(grid.length == 0) {
    		return 0;
    	}
    	int m = grid.length;
    	int n = grid[0].length;
    	backtrace(grid, 0, 0, 0, m, n, new boolean[m][n]);
    	return result;
    	
    }
    /**
     * -回溯主体,回溯超时
     */
    public void backtrace(int[][] grid, int currow, int curcol, int sums,int m, int n, boolean[][] visited) {
    	if(currow == m && curcol == n) {
    		result = Math.max(result, sums);
    	}
    	
    	if(currow == n || curcol == n) {
    		return;
    	}
    	
    	sums += grid[currow][curcol];
    	visited[currow][curcol] = true;
    	
    	if(curcol < n) {
    		if(!visited[currow][curcol+1]) {
    			backtrace(grid, currow, curcol+1, sums, m, n, visited);
    		}
    	
    	}
    	if(currow < m) {
    		if(!visited[currow+1][curcol]) {
    			backtrace(grid, currow+1, curcol, sums, m, n, visited);
    		}
    	}
    	
    }
    
    /**
     * -解题思路，动态规划
     */
    public int maxValue_1(int[][] grid) {
    	int m = grid.length, n = grid[0].length;
    	for(int i = 0; i < m; i++) {
    		for(int j = 0; j < n; j++) {
    			if(i == 0 && j == 0) {
    				continue;
    			}
    			if(i == 0) {
    				grid[i][j] += grid[i][j-1];
    			}else if(j == 0) {
    				grid[i][j] += grid[i-1][j];
    			}else {
    				grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
    			}
    		}
    	}
    	
    	return grid[m-1][n-1];
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
